package org.apache.commons.graph.algorithms.spanning

import com.gitee.wsl.ext.set.pop
import com.gitee.wsl.ext.set.push
import org.apache.commons.graph.CommonsGraph
import org.apache.commons.graph.Graph
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.SpanningTree
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.model.MutableSpanningTree
import org.apache.commons.graph.utils.Assertions
import org.apache.commons.graph.weight.OrderedMonoid

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Spanning Tree source selector.
 *
 * @param <V> the Graph vertices type
 * @param <W> the weight type
 * @param <WE> the Graph weighted edges type
</WE></W></V> */
interface SpanningTreeSourceSelector<V, W, WE> {
    /**
     * Applies the [Reverse-Delete](https://en.wikipedia.org/wiki/Reverse-Delete_algorithm) algorithm.
     *
     * <pre>
     * function ReverseDelete(edges[] E)
     * sort E in decreasing order
     * Define an index i = 0
     * while i < size(E)
     * Define edge temp = E[i]
     * delete E[i]
     * if temp.v1 is not connected to temp.v2
     * E[i] = temp
     * i = i + 1
     * return edges[] E
    </pre> *
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the weight operations
     * @return the calculated spanning tree
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingReverseDeleteAlgorithm(weightOperations: WO): SpanningTree<V, WE, W>

    /**
     * Selects an arbitrary source from the input Graph to calculate the spanning tree.
     *
     * @return the linked spanning tree algorithm builder
     */
    fun fromArbitrarySource(): SpanningTreeAlgorithmSelector<V, W, WE>

    /**
     * Allows specify a source vertex to calculate the spanning tree.
     *
     * @param source the source vertex to calculate the spanning tree.
     * @return the linked spanning tree algorithm builder
     */
    fun <S : V> fromSource(source: S): SpanningTreeAlgorithmSelector<V, W, WE>
}


/**
 * [SpanningTreeSourceSelector] implementation.
 *
 * @param <V> the Graph vertices type
 * @param <W> the weight type
 * @param <WE> the Graph weighted edges type
</WE></W></V> */
internal class DefaultSpanningTreeSourceSelector<V, W, WE>(
    private val graph: Graph<V, WE>,
    private val weightedEdges: Mapper<WE, W>
) : SpanningTreeSourceSelector<V, W, WE> {
    /**
     * {@inheritDoc}
     */
    override fun <WO : OrderedMonoid<W>> applyingReverseDeleteAlgorithm(weightOperations: WO): SpanningTree<V, WE, W> {
//        Assertions.checkNotNull(
//            weightOperations,
//            "The Reverse-Delete algorithm cannot be calulated with null weight operations"
//        )

        val sortedEdge = sortedSetOf(WeightedEdgesComparator(weightOperations, weightedEdges).reversed())

        //val sortedEdge: Queue<WE> = PriorityQueue(11, Collections.reverseOrder(WeightedEdgesComparator(weightOperations, weightedEdges)))
        val visitedEdge: MutableList<WE> = ArrayList()

        val edges = graph.edges
        for (we in edges) {
            //sortedEdge.offer(we)
            sortedEdge.push(we)
        }

        val tmpGraph: Graph<V, WE> = ReverseDeleteGraph(graph, sortedEdge, visitedEdge)

        while (!sortedEdge.isEmpty()) {
            //val we = sortedEdge.poll()
            val we = sortedEdge.pop()

            val vertices = graph.getVertices(we)

            try {
                CommonsGraph.findShortestPath(tmpGraph)
                    .whereEdgesHaveWeights(weightedEdges)
                    .from(vertices!!.head)
                    .to<V>(vertices.tail)
                    .applyingDijkstra<WO>(weightOperations)
            } catch (ex: PathNotFoundException) {
                // only if a path doesn't exist
                visitedEdge.add(we)
            }
        }

        val res = MutableSpanningTree<V, WE, W>(weightOperations, weightedEdges)
        for (v in graph.vertices) {
            res.addVertex(v)
        }

        for (we in edges) {
            val pair = tmpGraph.getVertices(we)
            if (pair != null) {
                res.addEdge(pair.head, we, pair.tail)
            }
        }

        return res
    }

    /**
     * {@inheritDoc}
     */
    override fun fromArbitrarySource(): SpanningTreeAlgorithmSelector<V, W, WE> {
        Assertions.checkState(graph.order > 0, "Spanning tree cannot be calculated on an empty graph")
        return fromSource(graph.vertices.iterator().next())
    }

    /**
     * {@inheritDoc}
     */
    override fun <S : V> fromSource(source: S): SpanningTreeAlgorithmSelector<V, W, WE> {
        //var source = source
        //source = Assertions.checkNotNull(source, "Spanning tree cannot be calculated without expressing the source vertex")
        require(graph.containsVertex(source)){ "Vertex $source does not exist in the Graph" }
        return DefaultSpanningTreeAlgorithmSelector(graph, weightedEdges, source)
    }
}
